﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using KLadderProposal.Interfaces;
using KLadderProposal.Interfaces.BasicStructures;

namespace KLadderProposal.Algorithms
{
    //Description:
    /*
     * Algorithm go over all the nodes and for each pair of neigbors checks the threshold condition.
     * If the condition is valid, the above neigbors should belong to the same cluster.
     * Special case: 
     * When the condition is valid and two neigbors already belong to different clusters (so we need to union those clusters): 
     * In this case we organize their cluster numbers in the collection and in the end of the algorithm we update the nodes with 
     * new cluster numbers according to that collection. 
     */ 
    //clique can be found when threshold = number of nodes of clique - 2
    public class JaccardBasedAlgorithm : IAlgorithm
    {
        private int _theshold = 100;
        private bool _isParallel;
        private int _nextClusterNumber = 0;
        private Random _rand = new Random();
        private List<GraphNode> _connectedNodes = new List<GraphNode>();

        //determines the threshold - minimum number of the common neigbors (required for two neigbors to belong to the same cluster) 
        public int Threshold
        {
            get { return _theshold; }
            set { _theshold = value; }
        }

        public bool IsParallel
        {
            get { return _isParallel; }
            set { _isParallel = value; }
        }

        //determines whether to run basic or advanced version of the algorithm
        private bool _runCommonVertexSearchStep = false;
        public bool RunCommonVertexSearchStep
        {
            get { return _runCommonVertexSearchStep; }
            set { _runCommonVertexSearchStep = value; }
        }

        public void Run(IGraph graph)
        {
            System.Diagnostics.Stopwatch stopwatch = new System.Diagnostics.Stopwatch();
            stopwatch.Start();
            Dictionary<int, HashSet<int>> sameClusterNumbers = new Dictionary<int, HashSet<int>>();

            List<GraphNode> graphNodes = new List<GraphNode>(graph.Nodes.Where(node => !node.IsMarkedAsDeleted));
            for (int i = 0; i < graphNodes.Count; i++)
            {
                GraphNode graphNode = graphNodes[i];
                foreach (GraphNode neighbor in graphNode.Neighbors.Values.Where(node => !node.IsMarkedAsDeleted))
                {  
                    if (graphNode == neighbor)
                        continue;
                    
                    if (graphNode.ClusterNumbers[0] != 0 && graphNode.ClusterNumbers[0] == neighbor.ClusterNumbers[0])
                        continue;                                      

                    if (GetCommonNeigborsCount(graphNode, neighbor) >= Threshold)
                    {
                        if (graphNode.ClusterNumbers[0] == 0 && neighbor.ClusterNumbers[0] == 0)
                            graphNode.ClusterNumbers[0] = neighbor.ClusterNumbers[0] = ++_nextClusterNumber;
                        else if (graphNode.ClusterNumbers[0] > 0 && neighbor.ClusterNumbers[0] == 0)
                            neighbor.ClusterNumbers[0] = graphNode.ClusterNumbers[0];
                        else if (graphNode.ClusterNumbers[0] == 0 && neighbor.ClusterNumbers[0] > 0)
                            graphNode.ClusterNumbers[0] = neighbor.ClusterNumbers[0];
                        else
                        {
                            AddToSameClusterNumbers(sameClusterNumbers, graphNode.ClusterNumbers[0], neighbor.ClusterNumbers[0]);
                        }
                    }
                }
            }

            UpdateClusterNumbers(sameClusterNumbers, graph.Nodes.Where(node => !node.IsMarkedAsDeleted));

            if (RunCommonVertexSearchStep)
            {
                graph.Nodes.ToList().ForEach(node =>
                {
                    if (node.ClusterNumbers[0] == 0)
                        node.ClusterNumbers[0] = -1;
                });

                var clusters = from graphNode in graph.Nodes.Where(node => !node.IsMarkedAsDeleted)
                               where graphNode.ClusterNumbers[0] > 0 && graphNode.ClusterNumbers.Count == 1
                               group graphNode by graphNode.ClusterNumbers[0] into g
                               select new ClusterDetails { ClusterNumber = g.Key, ClusterNodes = g.ToList() };

                List<GraphNode> nodesWithMultipleClustres = graph.Nodes.Where(node => !node.IsMarkedAsDeleted && node.ClusterNumbers.Count > 1).ToList();
                foreach (var node in nodesWithMultipleClustres)
                {
                    foreach(int clusterNumber in node.ClusterNumbers)
                    {
                        ClusterDetails details = clusters.SingleOrDefault(cluster => cluster.ClusterNumber == clusterNumber);
                        if(details == null)
                            details = new ClusterDetails{ ClusterNumber = clusterNumber, ClusterNodes = new List<GraphNode>()};

                        details.ClusterNodes.Add(node);
                    }
                }
                

                TryToDivideClusters(clusters);


                graph.Nodes.ToList().ForEach(node =>
                {
                    if (node.ClusterNumbers[0] == -1)
                        node.ClusterNumbers[0] = 0;
                });
            }

            stopwatch.Stop();
        }

        private void TryToDivideClusters(IEnumerable<ClusterDetails> clusters)
        {
            if (IsParallel)
            {
                Parallel.ForEach(clusters, group =>
                {
                    if (group.ClusterNodes.Count > 1)
                        TryToDivideClustersHelper(group);
                });
            }
            else
            {
                foreach (var group in clusters)
                {
                    if(group.ClusterNodes.Count > 1)
                        TryToDivideClustersHelper(group);
                }
            }
        }

        private void TryToDivideClustersHelper(ClusterDetails group)
        {
            if (TryToDivideCluster(group.ClusterNodes, group.ClusterNumber))
            {
                var newClusters = (from graphNode in @group.ClusterNodes
                                   where graphNode.ClusterNumbers.Count == 1
                                   group graphNode by graphNode.ClusterNumbers[0] into g
                                   select new ClusterDetails { ClusterNumber = g.Key, ClusterNodes = g.ToList() }).ToList();

                List<GraphNode> nodesWithMultipleClustres = @group.ClusterNodes.Where(node => node.ClusterNumbers.Count > 1).ToList();
                foreach (var node in nodesWithMultipleClustres)
                {
                    foreach (int clusterNumber in node.ClusterNumbers)
                    {
                        ClusterDetails details = newClusters.SingleOrDefault(cluster => cluster.ClusterNumber == clusterNumber);
                        if (details == null)
                            details = new ClusterDetails { ClusterNumber = clusterNumber, ClusterNodes = new List<GraphNode>() };

                        details.ClusterNodes.Add(node);
                    }
                }

                TryToDivideClusters(newClusters);
            }
        }

        private bool TryToDivideCluster(List<GraphNode> clusterNodes, int clusterNumber)
        {
            Dictionary<int, HashSet<int>> sameClusterNumbers = new Dictionary<int, HashSet<int>>();
            int indexOfNodeToDelete = 0;
            int countOfDistinctClusters = 1;
            Dictionary<string, List<int>> initialClusterNumbers = new Dictionary<string, List<int>>();
            //save initial cluster numbers
            initialClusterNumbers = clusterNodes.ToDictionary(node => node.Label, node => new List<int>(node.ClusterNumbers));

            while (indexOfNodeToDelete < clusterNodes.Count && countOfDistinctClusters == 1)
            {
                sameClusterNumbers.Clear();
                clusterNodes.ForEach(node =>
                    {
                        node.TempClusterNumber = 0;
                        node.ClusterNumbers.Clear();
                    });
                clusterNodes[indexOfNodeToDelete].IsMarkedAsDeleted = true;
            
                //performace improvement can be made by running dfs on neighbors of the deleted node (only those in the same cluster)
                List<GraphNode> neighborsOfNodeToDelete = new List<GraphNode>(
                    clusterNodes[indexOfNodeToDelete].Neighbors.Values.Where(node=>clusterNodes.Contains(node)));
                if (neighborsOfNodeToDelete.Count > 0)
                {
                    List<GraphNode> connectedNeighborsAfterDeletion = new List<GraphNode>();
                    FindAllConnectedNotRecursive(neighborsOfNodeToDelete[0], neighborsOfNodeToDelete, connectedNeighborsAfterDeletion);
                    if (connectedNeighborsAfterDeletion.Count == neighborsOfNodeToDelete.Count)//all the neigbors still connected?
                    {
                        clusterNodes[indexOfNodeToDelete].IsMarkedAsDeleted = false;
                        neighborsOfNodeToDelete.ForEach(node => node.IsVisited = false);
                        indexOfNodeToDelete++;
                        continue;
                    }

                    var notconnected = neighborsOfNodeToDelete.Except(connectedNeighborsAfterDeletion).ToList();
                    neighborsOfNodeToDelete.ForEach(node => node.IsVisited = false);
                }

                for (int i = 0; i < clusterNodes.Count; i++)
                {
                    if (i == indexOfNodeToDelete)
                        continue;

                    GraphNode graphNode = clusterNodes[i];
                    foreach (GraphNode neighbor in graphNode.Neighbors.Values.Where(node => !node.IsMarkedAsDeleted))
                        //&& node.ClusterNumbers > -1))
                    {
                        if (graphNode == neighbor)
                            continue;

                        if (graphNode.TempClusterNumber != 0 && graphNode.TempClusterNumber == neighbor.TempClusterNumber)
                            continue;

                        if (!clusterNodes.Contains(neighbor))
                            continue;

                        if (GetCommonNeigborsCount(graphNode, neighbor) >= Threshold)//(Threshold - 1))//-1 for cliques
                        {
                            if (graphNode.TempClusterNumber == 0 && neighbor.TempClusterNumber == 0)
                            {
                                int nextClusterNumberInner = Interlocked.Increment(ref _nextClusterNumber);
                                graphNode.TempClusterNumber = neighbor.TempClusterNumber = nextClusterNumberInner;
                            }
                            else if (graphNode.TempClusterNumber > 0 && neighbor.TempClusterNumber == 0)
                                neighbor.TempClusterNumber = graphNode.TempClusterNumber;
                            else if (graphNode.TempClusterNumber == 0 && neighbor.TempClusterNumber > 0)
                                graphNode.TempClusterNumber = neighbor.TempClusterNumber;
                            else
                            {
                                AddToSameClusterNumbers(sameClusterNumbers, graphNode.TempClusterNumber, neighbor.TempClusterNumber);
                            }
                        }
                    }
                } 
                
                foreach (GraphNode gn in clusterNodes)
                    gn.ClusterNumbers[0] = gn.TempClusterNumber;

                UpdateClusterNumbers(sameClusterNumbers, clusterNodes.Where(node => !node.IsMarkedAsDeleted));

                clusterNodes[indexOfNodeToDelete].IsMarkedAsDeleted = false;

                List<int> distinctClusterNumbers = clusterNodes.Where(node => node.ClusterNumbers[0] > 0).
                    Select(node => node.ClusterNumbers[0]).Distinct().ToList();

                countOfDistinctClusters = distinctClusterNumbers.Count;               

                SetCommonNodeClusterNumber(clusterNodes, indexOfNodeToDelete, countOfDistinctClusters);

                indexOfNodeToDelete++;
            }

            if (countOfDistinctClusters == 1)
            {
                //back to initial cluster numbers
                foreach (GraphNode node in clusterNodes)
                    node.ClusterNumbers = initialClusterNumbers[node.Label];
            }
            else
            {
                //return multiple cluster numbers
                foreach (GraphNode node in clusterNodes)
                    if (initialClusterNumbers[node.Label].Count > 1)
                    {
                        node.ClusterNumbers.AddRange(initialClusterNumbers[node.Label]);
                        node.ClusterNumbers.Remove(clusterNumber);
                    }
            }

            return countOfDistinctClusters > 1;
        }

        private void SetCommonNodeClusterNumber(List<GraphNode> clusterNodes, int indexOfNodeToDelete, int countOfDistinctClusters)
        {
            if (countOfDistinctClusters > 1)
                foreach (GraphNode neighborOfNode in clusterNodes[indexOfNodeToDelete].Neighbors.Values.
                    Where(node => !node.IsMarkedAsDeleted))
                {
                    if (clusterNodes[indexOfNodeToDelete] == neighborOfNode)//cdc40 cdc40 relation in sac file
                        continue;

                    if (GetCommonNeigborsCount(clusterNodes[indexOfNodeToDelete], neighborOfNode) >= Threshold)
                    {
                        clusterNodes[indexOfNodeToDelete].ClusterNumbers.AddRange(neighborOfNode.ClusterNumbers);
                    }
                }
            else
                clusterNodes[indexOfNodeToDelete].ClusterNumbers.Add(clusterNodes[1].ClusterNumbers[0]);

            clusterNodes[indexOfNodeToDelete].ClusterNumbers = clusterNodes[indexOfNodeToDelete].ClusterNumbers.Distinct().ToList();
            clusterNodes[indexOfNodeToDelete].ClusterNumbers.Remove(0);
        }

        private void UpdateClusterNumbers(Dictionary<int, HashSet<int>> sameClusterNumbers, IEnumerable<GraphNode> graphNodes)
        {
            foreach (GraphNode graphNode in graphNodes)
            {
                foreach (KeyValuePair<int, HashSet<int>> pair in sameClusterNumbers)
                {
                    for (int i = graphNode.ClusterNumbers.Count - 1; i >= 0; i--)
                    {
                        if (pair.Value.Contains(graphNode.ClusterNumbers[i]))
                        {
                            graphNode.ClusterNumbers[i] = pair.Key;
                            break;
                        }
                    }

                    if (graphNode.ClusterNumbers.Count > 1)
                    {
                        if (graphNode.ClusterNumbers.Distinct().ToList().Count == 1)//all the same, remain only one
                        {
                            graphNode.ClusterNumbers.RemoveRange(1, graphNode.ClusterNumbers.Count - 1);
                        }
                    }
                }
            }
        }

        private void 
            AddToSameClusterNumbers(Dictionary<int, HashSet<int>> sameClusterNumbers, int clusterNumber1, int clusterNumber2)
        {
            HashSet<int> listOfClusterNumber1;
            HashSet<int> listOfClusterNumber2;

            sameClusterNumbers.TryGetValue(clusterNumber1, out listOfClusterNumber1);
            sameClusterNumbers.TryGetValue(clusterNumber2, out listOfClusterNumber2);

            if (listOfClusterNumber1 == null)
                listOfClusterNumber1 = new HashSet<int>();

            if (listOfClusterNumber2 == null)
                listOfClusterNumber2 = new HashSet<int>();

            if (listOfClusterNumber1.Count > 0 && listOfClusterNumber2.Count > 0)
            {
                listOfClusterNumber1.Add(clusterNumber2);
                listOfClusterNumber1.UnionWith(listOfClusterNumber2);
                sameClusterNumbers.Remove(clusterNumber2);
            }
            else if (listOfClusterNumber1.Count > 0)
            {
                if (!listOfClusterNumber1.Contains(clusterNumber2))
                    listOfClusterNumber1.Add(clusterNumber2);

                List<int> keysToUnit = new List<int>(); 
                foreach (KeyValuePair<int, HashSet<int>> pair in sameClusterNumbers)
                {
                    if (pair.Key == clusterNumber1)
                        continue;

                    if (pair.Value.Contains(clusterNumber2))
                        keysToUnit.Add(pair.Key);
                }

                if(keysToUnit.Count > 0)
                    foreach (int keyToUnit in keysToUnit)
                    {
                        //listOfClusterNumber1.Add(clusterNumber2); already done
                        listOfClusterNumber1.UnionWith(sameClusterNumbers[keyToUnit]);
                        sameClusterNumbers.Remove(keyToUnit);
                    }
            }
            else if (listOfClusterNumber2.Count > 0)
            {
                if (!listOfClusterNumber2.Contains(clusterNumber1))
                    listOfClusterNumber2.Add(clusterNumber1);

                List<int> keysToUnit = new List<int>();
                foreach (KeyValuePair<int, HashSet<int>> pair in sameClusterNumbers)
                {
                    if (pair.Key == clusterNumber2)
                        continue;

                    if (pair.Value.Contains(clusterNumber1))
                        keysToUnit.Add(pair.Key);
                }

                if (keysToUnit.Count > 0)
                    foreach (int keyToUnit in keysToUnit)
                    {
                        //listOfClusterNumber2.Add(clusterNumber2); already done
                        listOfClusterNumber2.UnionWith(sameClusterNumbers[keyToUnit]);
                        sameClusterNumbers.Remove(keyToUnit);
                    }
            }
            else
            {
                bool isAdded = false;
                int keyWhereAdded = 0;
                foreach (var pair in sameClusterNumbers) //779,778;780,778
                {
                    if (pair.Value.Contains(clusterNumber1))
                    {
                        pair.Value.Add(clusterNumber2);
                        isAdded = true;
                        keyWhereAdded = pair.Key;
                        break;
                    }
                    else if (pair.Value.Contains(clusterNumber2))
                    {
                        pair.Value.Add(clusterNumber1);
                        isAdded = true;
                        keyWhereAdded = pair.Key;
                        break;
                    }
                }
                if (!isAdded)
                    sameClusterNumbers.Add(clusterNumber1, new HashSet<int> { clusterNumber1, clusterNumber2 });
                else 
                {
                    List<int> keysToUnit = new List<int>();
                    foreach (KeyValuePair<int, HashSet<int>> pair in sameClusterNumbers)
                    {
                        if (pair.Key == keyWhereAdded)
                            continue;

                        if (pair.Value.Contains(clusterNumber1) || pair.Value.Contains(clusterNumber2))
                            keysToUnit.Add(pair.Key);
                    }

                    if (keysToUnit.Count > 0)
                        foreach (int keyToUnit in keysToUnit)
                        {
                            //listOfClusterNumber2.Add(clusterNumber2); already done
                            sameClusterNumbers[keyWhereAdded].UnionWith(sameClusterNumbers[keyToUnit]);
                            sameClusterNumbers.Remove(keyToUnit);
                        }
                }
            }
        }

        private int GetCommonNeigborsCount(GraphNode graphNode, GraphNode neighbor)
        {
            int commonNeighborsCount = 0;
            int i = 0, j = 0;

            while (i < graphNode.Neighbors.Count && j < neighbor.Neighbors.Count)
            {
                string label1 = graphNode.Neighbors.Values[i].Label;
                string label2 = neighbor.Neighbors.Values[j].Label;

                int comparisonResult = label1.CompareTo(label2);
                if (comparisonResult == 0)
                {
                    commonNeighborsCount++;
                    i++;
                    j++;
                }
                else if (comparisonResult > 0)
                    j++;
                else
                    i++;
            }

            return commonNeighborsCount;
        }

        private int GetCommonNeigborsCountOld(GraphNode graphNode, GraphNode neighbor)
        {
            int commonNeighborsCount = 0;
            foreach (GraphNode graphNodeNeighbor in graphNode.Neighbors.Values)
                foreach (GraphNode neighborNeighbor in neighbor.Neighbors.Values)
                {
                    if (graphNodeNeighbor == neighborNeighbor)
                        continue;

                    if (graphNodeNeighbor.Label.CompareTo(neighborNeighbor.Label) == 0)
                        commonNeighborsCount++;
                }

            return commonNeighborsCount;
        }

        public void FindAllConnected(GraphNode node, List<GraphNode> relevantNodes)
        {
            node.IsVisited = true;
            _connectedNodes.Add(node);

            foreach (GraphNode neighbor in node.Neighbors.Values.Where(temp => relevantNodes.Contains(temp)))
                if (!neighbor.IsVisited)
                    FindAllConnected(neighbor, relevantNodes);
        }

        public void FindAllConnectedNotRecursive(GraphNode node, List<GraphNode> relevantNodes, List<GraphNode> connectedNodes)
        {
            var stack = new Stack<GraphNode>();
            var visitedNodes = new HashSet<GraphNode>();
            stack.Push(node);
            while (stack.Count > 0)
            {
                var curr = stack.Pop();
                if (!visitedNodes.Contains(curr))
                {
                    visitedNodes.Add(curr);
                    connectedNodes.Add(curr);

                    foreach (var next in curr.Neighbors.Values.Where(temp => relevantNodes.Contains(temp)))
                    {
                        if (!visitedNodes.Contains(next))
                            stack.Push(next);
                    }
                }
            }
        }
    }

    public class ClusterDetails
    {
        public int ClusterNumber { get; set; }
        public List<GraphNode> ClusterNodes { get; set; }
    }
}



//private bool TryToDivideClusterOld(List<GraphNode> clusterNodes)
//        {
//            int clusterNumber = clusterNodes[0].ClusterNumber;
//            bool result = false;

//            for (int i = 0; i < clusterNodes.Count; i++)
//            {
//                GraphNode graphNode = clusterNodes[i];
//                foreach (GraphNode neighbor in graphNode.Neighbors.Values)
//                {
//                    if (neighbor.ClusterNumber != clusterNumber)//neigbor did not pass initial threshold-->in different cluster
//                        continue;

//                    foreach (GraphNode neighborOfNeighbor in neighbor.Neighbors.Values)
//                    {
//                        if (neighborOfNeighbor.ClusterNumber != clusterNumber)//neigbor of neighbor did not pass initial threshold-->in different cluster
//                            continue;

//                        if (GetCommonNeigborsCount(graphNode, neighborOfNeighbor) > _theshold)
//                        {
//                            if (graphNode.ClusterNumber != neighborOfNeighbor.ClusterNumber) // one of the nodes got earlier a new cluster number
//                            {
//                                if (graphNode.ClusterNumber > neighborOfNeighbor.ClusterNumber)
//                                {                                    
//                                    foreach (GraphNode neighborOfNeighborNeighbor in neighborOfNeighbor.Neighbors.Values)
//                                    {
//                                        if (neighborOfNeighborNeighbor.ClusterNumber == neighborOfNeighbor.ClusterNumber)
//                                            neighborOfNeighborNeighbor.ClusterNumber = graphNode.ClusterNumber;
//                                    }
//                                    neighborOfNeighbor.ClusterNumber = graphNode.ClusterNumber;
//                                }
//                                else 
//                                {
//                                    foreach (GraphNode graphNodeNeighbor in graphNode.Neighbors.Values)
//                                    {
//                                        if (graphNodeNeighbor.ClusterNumber == graphNode.ClusterNumber)
//                                            graphNodeNeighbor.ClusterNumber = neighborOfNeighbor.ClusterNumber;
//                                    }
//                                    graphNode.ClusterNumber = neighborOfNeighbor.ClusterNumber; 
//                                }
//                            }
//                        }
//                        else
//                        {
//                            neighborOfNeighbor.ClusterNumber = _nextClusterNumber++;
//                            result = true;
//                        }
//                    }
//                }
//            }

//            return result;
//        }




//private bool TryToDivideCluster(List<GraphNode> clusterNodes)
//        {
//            int clusterNumber = clusterNodes[0].ClusterNumber;
//            bool result = false;
//            _sameClusterNumbers.Clear();

//            for (int j = 0; j < clusterNodes.Count; j++)
//            {
//                if (j > 0)
//                    clusterNodes[j - 1].IsMarkedAsDeleted = false;
//                clusterNodes[j].IsMarkedAsDeleted = true;

//                List<GraphNode> notDeletedNodes = clusterNodes.Where(node => !node.IsMarkedAsDeleted).ToList();
//                for (int i = 0; i < notDeletedNodes.Count; i++)
//                {
//                    GraphNode graphNode = clusterNodes[i];
//                    foreach (GraphNode neighbor in graphNode.Neighbors.Values.Where(node => !node.IsMarkedAsDeleted && 
//                        (node.ClusterNumber == clusterNumber || node.ClusterNumber > clusterNumber)))
//                    {
//                        if (graphNode.ClusterNumber != clusterNumber && graphNode.ClusterNumber == neighbor.ClusterNumber)
//                            continue;

//                        if (GetCommonNeigborsCount(graphNode, neighbor) > _theshold)
//                        {
//                            if (graphNode.ClusterNumber == clusterNumber && neighbor.ClusterNumber == clusterNumber)
//                                graphNode.ClusterNumber = neighbor.ClusterNumber = _nextClusterNumber++;
//                            else if (graphNode.ClusterNumber > clusterNumber && neighbor.ClusterNumber == clusterNumber)
//                                neighbor.ClusterNumber = graphNode.ClusterNumber;
//                            else if (graphNode.ClusterNumber == clusterNumber && neighbor.ClusterNumber > clusterNumber)
//                                graphNode.ClusterNumber = neighbor.ClusterNumber;
//                            else
//                            {
//                                AddToSameClusterNumbers(graphNode.ClusterNumber, neighbor.ClusterNumber);
//                            }
//                        }
//                        else
//                        { 
//                            //???were in the same cluster but after this iteration not any more
//                        }
//                    }
//                }
//            }

//            return result;
//        }